import java.util.List;

/**
 * Created by L.jp
 * Description:将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
 * 如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
 * 你不能更改节点中的值，只能更改节点本身。
 * User: 86189
 * Date: 2022-05-10
 * Time: 17:21
 */
//class ListNode {
//    int val;
//    ListNode next = null;
//}
public class Solution {
    /*我们要翻转完整个链表，那么就需要翻转每k个为一组的链表，翻转完一组之后，原来每一组的头结点的就变为了
    * 翻转后每一组的最后一个节点，也是作为连接下一组的节点，这也是递归的关键，每一组都是这样*/
    //方法： 1.循环k次，找到每一组的尾结点的下一个位置，作为下一组翻转的开始的地方，也是每一次递归的头部
    //      2.找到位置之后就从每一组的头部开始翻转，使用双指针法
    public ListNode reverseKGroup (ListNode head, int k) {
        ListNode tail=head;
        //找到第k+1个位置，作为每一组开始反转的头部
        for(int i = 0; i < k; i++){
            if(tail==null){
                return head;
            }
            tail=tail.next;
        }
        //从每一组的头部开始反转，跟反转整个链表的迭代法是一样的
        //借助一个空的节点
        ListNode prev=null;
        //当前节点
        ListNode cur=head;
        //当前节点没有到达该组的尾部
        while (cur != tail) {
            //先记录下一个节点
            ListNode tmp=cur.next;
            cur.next=prev; //反转
            prev=cur;
            cur=tmp;
        }
        //反转完一组之后，就到了下一组，递归下去
        //翻转后当前组的开头节点就连接着下一组的没有翻转的开头结点
        head.next=reverseKGroup(tail,k); //tail就是下一组待反转的头结点
        return prev; //prev就是翻转后每一组的头结点
    }
}
